package second;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution {

    public void duplicateZeros(int[] arr) {
        int div = -1, cur = 0, len = arr.length;
        for (; cur < len; cur++){
            if (arr[cur] == 0){
                div += 2;
            }else {
                div += 1;
            }

            if (div >= len - 1){
                break;
            }
        }

        //处理特殊情况
        if (div == len){
            arr[div - 1] = 0;
            div -= 2;
            cur--;
        }

        //重写
        for (; cur >= 0; cur--){
            if (arr[cur] == 0){
                arr[div] = 0;
                arr[div - 1] = 0;
                div -= 2;
            }else {
                arr[div] = arr[cur];
                div -= 1;
            }
        }
    }

    public List<List<Integer>> threeSum(int[] n) {
        Arrays.sort(n);
        int len = n.length;
        List<List<Integer>> ret = new ArrayList<>();

        for (int c = len - 1; c >= 2;){
            int a = 0, b = c - 1, target = -n[c];

            while (a < b){
                if (n[a] + n[b] > target){
                    b--;

                    while (b > 0 && b < len && n[b] == n[b + 1]){
                        b--;
                    }
                }else if (n[a] + n[b] < target){
                    a++;

                    while (a > 0 && a < len && n[a] == n[a - 1]){
                        a++;
                    }
                }else {
                    List<Integer> tmp = new ArrayList<>();
                    tmp.add(n[a]);
                    tmp.add(n[b]);
                    tmp.add(n[c]);

                    a++;

                    while (a > 0 && a < len && n[a] == n[a - 1]){
                        a++;
                    }
                }
            }

            c--;
            while (c > 0 && c < len && n[c] == n[c + 1]){
                c--;
            }
        }

        return ret;
    }
    public static void main(String[] args) {
        Solution test = new Solution();
        //test.duplicateZeros(new int[]{0,0,0,0,0,0,0});
        test.threeSum(new int[]{-4, -1, -1, 1, 2, 0});
    }
}
